package arithmetic.sort;

/**
 * 快速排序
 * <p>
 *
 * @author cuihao
 * @date 2018/1/31
 */
public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int left = low, right = high;
        int index = arr[low];
        while (left < right) {
            while (left < right && arr[right] >= index) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right];
            }
            left++;
            while (left < right && arr[left] <= index) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left];
            }
            right--;
        }
        arr[left] = index;
        quickSort(arr, low, left - 1);
        quickSort(arr, left + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {12, 54, 12, 1, 345, 9, 62, 415, 10, 2, 12};
        quickSort(arr, 0, arr.length - 1);
        for (int m = 0; m < arr.length; m++) {
            System.out.println(arr[m]);
        }
    }
}
